#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void Qsort(float * x,float * y,int * n,int a,int b)
{
  if(b-a<1) return;
  int i,j,tr;
  srand(time(NULL));
  int r=rand()%(b-a)+a;
  float temp;
  temp=x[a]; x[a]=x[r]; x[r]=temp;
  temp=y[a]; y[a]=y[r]; y[r]=temp;
  tr=n[a]; n[a]=n[r]; n[r]=tr;
  float t=x[a];
  i=a-1; j=b+1;
  
  while(1)
  {
   do {i++;} while(i<=b && x[i]<=t);
   do {j--;} while(j>a && x[j]>=t);
   if(i>=j) break;
   temp=x[i]; x[i]=x[j]; x[j]=temp;
   temp=y[i]; y[i]=y[j]; y[j]=temp;
   tr=n[i]; n[i]=n[j]; n[j]=tr;
  }
  temp=x[a]; x[a]=x[j]; x[j]=temp;
  temp=y[a]; y[a]=y[j]; y[j]=temp;
  tr=n[a]; n[a]=n[j]; n[j]=tr;
  Qsort(x,y,n,a,j-1);
  Qsort(x,y,n,j+1,b);  
}//对p点按照x的大小进行排序。

void Select(float *px,float *py,int *pn,float sx1,float sy1,float sx2,float sy2,int k,char **A,int n)
{
  int i=0,j=n-1;
  int t1=n/2;
  int t2=n/2;
  while(1)
  {
    
    if(px[t1]<=sx1 && px[t1+1]<=sx1)
    {
      if(t1==n-1) 
        break;
      i=t1;
      if(t1>=(j-i)/2+i)
        t1++;
      else 
        t1=(j-i)/2+i;
    }
    else if(px[t1]>=sx1 && px[t1+1]>=sx1)
    {
      if(t1==0)
        break;
      j=t1;
      if(t1<=(j-i)/2+i)
        t1--;
      else 
        t1=(j-i)/2+i;
    }
    else if(px[t1]<=sx1 && px[t1+1]>=sx1)
    {
      t1++;
      break;
    }
    
  }//确定sx1在数字点中的位置
  
  while(1)
  {
    if(px[t2]<=sx2 && px[t2+1]<=sx2)
    {
      if(t2==n-1) 
        break;
      i=t2;
      if(t2>=(j-i)/2+i)
        t2++;
      else 
        t2=(j-i)/2+i;
    }
    else if(px[t2]>=sx2 && px[t2+1]>=sx2)
    {
      if(t2==0)
        break;
      j=t2;
      if(t2<=(j-i)/2+i)
        t2--;
      else
        t2=(j-i)/2+i;
    }
    else if(px[t2]<=sx2 && px[t2+1]>=sx2)
      break;
    
  }//确定sx2在数字点中的位

  for(i=t1;i<=t2;i++)
  {
    if(py[i]<=sy2&&py[i]>=sy1)//表明p点在s幻灯片内
      A[k][pn[i]]='1';
  }
}